#include<stdio.h>
#include<stdlib.h>
#include<iostream>
using namespace std;
#define ERROR 0
#define OK 1
#define ElemType int
#define Status int

typedef struct LNode{
	ElemType data;
	struct LNode *next;
}LNode, *LinkList; 

//循环链表：是一种头尾相接的链表(即：表中最后一个结点的指针域指向头结点，整个链表形成一个环) 
//优点：从表中任一结点出发均可找到表中其他结点
//注意：循环链表中没有NULL指针，故涉及遍历操作时，其终止条件就不像非循环链表那样判断p或p->next是否为空
//      而是判断它们是否等于头指针  p != L; p->next != L; (单循环链表)

//头指针表示单循环链表(a1: L->next)  尾指针表示单循环链表(a1: R->next->next)


//带 尾指针 循环链表合并(将Tb合并在Ta之后)
//操作：1.p存表头结点 2.Tb表头连接到Ta表尾 3.释放Tb表头结点  4.修改指针 
//p = Ta->next;
//Ta->next = Tb->next->next;
//delete(Tb->next);
//Tb->next = p;
LinkList Connect(LinkList Ta, LinkList Tb){
	//假设Ta、Tb都是非空的单循环链表
	LNode  *p = Ta->next;
	Ta->next = Tb->next->next;
	delete(Tb->next);
	Tb->next = p;
	return Tb;
}//时间复杂度O(1) 


//在单链表中，查找某结点的前驱结点的执行时间为O(1)
//可以用 双向链表来克服单链表的这种缺点。
//双向链表：在单链表的每个结点里增加一个指向其直接前驱的指针域 prior，这样链表中就形成了有两个方向不同的链 
//双向链表的结构定义如下：
typedef struct DuLNode{
	ElemType data;
	struct DuLNode *prior, *next;	
}DuLNode, *DuLinkList;


//双向循环链表：让头结点的前驱指针指向链表的最后一个结点，让最后一个结点的后继指针指向头结点 

//双向链表结构的对称性(设指针p指向某一结点) 
// 	p->prior->next =  p  =  p->next->prior

//在双向链表中有些操作(如: ListLength、GetElem等) ，因仅涉及一个方向的指针，故它们的算法与线性链表的相同。
//但在插入、删除时，则需同时修改两个方向上的指针，两者的操作的时间复杂度均为0(n)。

//双向链表的插入  在带头结点的双向循环链表L中的第i个位置之前插入元素e 
Status ListInsert_DuL(DuLinkList &L, int i, ElemType e){
	DuLNode *p = L;
	int j = 0;
	while(p && j < i){
		j++;
		p = p->next;
	}
	if(!p || j > i) return ERROR;
	DuLNode *s = new DuLNode;
	s->data = e;
	s->prior = p->prior; //1.新结点prior指向原结点前驱 
	p->prior->next = s;  //2.原结点前驱的next指针指向新结点 
	s->next = p;         //3.新结点next指向后结点 
	p->prior = s;		 //4.原结点prior指向新结点 
	return OK;
}


//双向链表的删除  删除带头结点的双向循环链表L的第i个元素，并用e返回
ElemType ListDelete_DuL(DuLNode *&L, int i, ElemType &e){
	DuLNode *p = L; 
	while(i){
		i--;
		p = p->next;
	}
	if(!p) return ERROR; 	  //查询操作时间复杂度：O(n) 
	e = p->data;
	p->prior->next = p->next;
	p->next->prior = p->prior;
	delete(p); //free(p);     //删除操作时间复杂度：O(1)
	return e; 
}


//链式存储结构的优点：
//	结点空间可以动态申请释放
//	数据元素的逻辑层次靠结点的指针来指示，插入和删除时不需要移动数据元素。
//链式存储结构的缺点：
//	存储密度小，每个结点的指针域需要额外占用存储空间。当每个结点的数据域所占字节不多时，指针域所占存储空间的比重显得很大
//   	存储密度：指结点数据本身所占的存储量和整个结点结构中所占的存储量之比。
//		存储密度 = 结点数据本身所占用的空间 / 结点占用的空间总量 
//	链式存储结构是非随机存取的结构。对任一结点的操作都要从头指针依指针链查找到该结点，这增加了算法的复杂度 


//顺序表的适用情况 
//  1.表长变化不大，且能事先确定变化的范围
//  2.很少进行插入或删除操作，经常按元素位置序号访问数据元素
//链表的适用情况
//	1.长度变化较大
//  2.频繁进行插入或删除操作 

 
void CreateList_H(LinkList &L, int n){
	L = new LNode;
	L->next = NULL;
	for(int i = 1; i <= n;i++){
		LNode *p = new LNode;
		printf("请输入第%d个结点的值：",i);
		cin>>p->data;
		p->next = L->next;
		printf("%d\n",p->next);
		L->next = p;
	}
}

void CreateList_R(LinkList &L, int n){
	L = new LNode;
	L->next = NULL;
	LNode *r = L;
	while(n){
		n--;
		LNode *s = new LNode;
		cin>>s->data;
		r->next = s;
		s->next = NULL;
		r = s;
	}
}

void DisputeList(LinkList L){
	printf("输出您刚才的链表：\n");
	LNode *p = L;
	while(p->next){
		p = p->next;
		printf("%d\n",p->data);
	}
}



int main(void)
{
	int length;
	puts("请输入您想要的链表长度(头插法)");
	scanf("%d", &length);
	LinkList myFirstLinkList;
	CreateList_H(myFirstLinkList, length);
	DisputeList(myFirstLinkList);
	printf("请输入您想要的链表长度(尾插法)\n");
	int len; 
	scanf("%d",&len);
	LinkList myRLinkList;
	CreateList_R(myRLinkList, len);
	DisputeList(myRLinkList);
	return 0;
}